package org.zlb.algorithm.distance;

/**
 * Levenshtein 距离
 * 
 * @author zhoulingbo
 * @date 2021/12/12
 */
public class Levenshtein {

    /**
     * Levenshtein Distance (Edit Distance) 算法，是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数
     * @param s1
     * @param s2
     * @return
     */
    public static int d(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        
        int[][] matrix = new int[m+1][n+1];
        
        for (int i=0; i<m+1; i++)
        {
            matrix[i][0] = i;
        }
        
        for (int i=0; i<n+1; i++)
        {
            matrix[0][i] = i;
        }

        for (int j=1; j<m+1; j++)
        {
            for (int k=1; k<n+1; k++)
            {
                int w = chars1[j-1] == chars2[k-1] ? 0 : 1;
                int x = Math.min(matrix[j-1][k]+1, matrix[j][k-1]+1);
                matrix[j][k] = Math.min(x, matrix[j-1][k-1]+w);
            }
        }
        
        int d = matrix[m][n];
        return d;
    }
    
    public static double similarity(String s1, String s2) {
        int d = d(s1, s2);
        int m = s1.length(), n = s2.length();
        double similarity = 1 - ((double)d / Math.max(m, n));
        return similarity;
    }
}
